package com.hyb.algorithm.data.struct.dp;

/**
 * @Author: huyanbing
 * @Date: 2021/8/21 2:51 下午
 * <p>
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/
 * <p>
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 */
public class CanPartition {


    public static void main(String[] args) {

    }


    public boolean canPartition(int[] nums) {
        int n = nums.length;

        if (n <= 0) {
            return false;
        }

        int sum = 0;

        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }

        //奇数不可能 有两个相等的子集
        if (sum % 2 != 0) {
            return false;
        }

        sum = sum / 2;

        // 放入 i个元素   结果等于sum 的状态 true 或者 false;
        boolean[][] dp = new boolean[n + 1][sum + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][sum];


    }


    public boolean canPartition2(int[] nums) {
        int n = nums.length;

        if (n <= 0) {
            return false;
        }

        int sum = 0;

        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }

        //奇数不可能 有两个相等的子集
        if (sum % 2 != 0) {
            return false;
        }

        sum = sum / 2;

        // 放入 i个元素   结果等于sum 的状态 true 或者 false;
        boolean[] dp = new boolean[sum + 1];

        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            //唯⼀需要注意的是 j 应该从后往前反向遍历，
            // 因为每个物品（或者说数 字）只能⽤⼀次，以免之前的结果影响其他的结果。
            for (int j = sum; j >= 1; j--) {
                if (j - nums[i - 1] >= 0) {
                    dp[j] = dp[j] || dp[j - nums[i - 1]];
                }
            }
        }

        return dp[sum];


    }
}
